Image-processing techniques may be used to detect shapes (e.g., lines, squares, or circles) in an image. Shape detection usually includes two steps: edge detection and edge tracing (also known as edge linking). Edge detection is a well-known technique for locating pictorially meaningful discontinuities in grayscale levels that correspond to, for example, a boundary between two different regions in the image. Following edge detection, tracing procedures may be used to assemble detected edge pixels into larger edges that correspond more closely to the edges of objects in the original image. Once the edges in the image have been derived, well-established classification techniques, such as Fourier-shape descriptors and generalized Hough transforms, may be used to recognize an object in the image.
In traditional practice, a threshold is applied to intensity gradients of the image to decide whether edges are present. Pixels having intensity gradients greater than the threshold are marked as parts of an edge, while pixels having intensity gradients below the threshold are considered non-edge pixels. It is, however, difficult to specify a threshold that can clearly separate edge pixels and non-edge pixels. A more sophisticated edge detector uses hysteresis thresholding and two thresholds, Tlow and Thigh, to detect the edges. Pixels having intensity gradients greater than Thigh are marked as strong-edge pixels while pixels having intensity gradients below Tlow are marked as non-edge pixels. Pixels having intensity gradients that are below Thigh but above Tlow, called weak-edge pixels, are considered edge pixels only if they are “connected to” (e.g., neighboring) a pixel having an intensity gradient above Thigh (i.e., a strong-edge pixel). A continuous edge curve may thus be traced from weak-edge pixels in the image to strong-edge pixels, thereby reconstructing a larger edge having noisy or obscured portions. This method may provide better-defined edges in the image and allow for the tracing of faint edges (as long as a neighboring strong-edge pixel is identified).
Conventional edge-tracing systems and methods recursively trace the path of the edge pixels identified in an image. If a pixel is marked as an edge pixel, its neighboring pixels are scanned. As described above, the neighboring pixels are considered edge pixels if their intensity gradients are greater than Tlow. The neighbor-scanning procedure repeats for all neighboring edge pixels (i.e., all neighbors having an intensity gradient greater than Tlow). This recursive approach is thus time consuming and requires a large memory. Additionally, because of the random nature of scanning for the neighboring pixels and the unpredictability of the direction in which the edge may run, it is impossible to predict, in advance, which parts of the image are needed to detect a current edge, and thus the whole image must ordinarily be accessible locally.
Processors having small internal memories (e.g., digital-signal processors) cannot store the entire image (or information associated with the image, such as pixel labels) locally. Such processors, therefore, need to continually access slow system memory (e.g., external memory) to fetch additional portions of the image; this results in slow processing speeds for the edge-tracing algorithms. Consequently, there is a need to facilitate quick fetching of image information from local memory and processing of this information for purposes of edge tracing without using system memory.